Non-volatile control unit data, for example, are stored on hardware memory components such as EEPROM or flash memories. Various data systems, i.e., memory layout strategies, are used for this purpose.
In a typical layout strategy the memory is divided into equal-sized blocks and the actual data are stored in these blocks. In addition to these data, management information is required for each block. The management information for a block may indicate, among other things, whether a block is free or occupied, the length of the data stored in the block, the check sum/cyclic redundancy check (CRC)) for the data, and so forth.
Such a block-oriented EEPROM file system is used in some control units. This type of layout strategy is also present in the file allocation table (FAT) file system for hard disks. Thus, the use of block-oriented file systems is not limited to EEPROM memories.
In a further layout strategy, the memory is divided into two segments, one segment being the active segment. New data are added in each case to the previously written data in the active segment. As soon as the active segment is full, the current data are saved in the passive segment. At that point the active and passive segments exchange roles, and the filled segment—which is then passive—may be erased. The latter segment is thus once again available for storage as soon as the segment—which is then active—is full. Such a system, which may also contain more than two segments, may prospectively be used in control units having flash memories.
A particular characteristic of such file systems is that there is no fixed association of a sector of the storage medium to the data stored at that location. Different data may be stored in the same sector on the storage medium at different times. Thus, to read a concrete datum from the storage medium, a mechanism is necessary in order to find the datum on the storage medium, i.e., to identify the sectors in which the datum is present at the given point in time.
For hard disks, so-called directories are typically used as a mechanism for finding data. These directories contain an association of an identifier for the datum, typically a file name, with a list of the blocks in which the datum is located.
In contrast, another mechanism in which each block contains information as to whether the block is free, or optionally, the identifier for the datum stored in the block (a number) is used in some control units having EEPROM memories. There are also data which are too large to store in a single block. Such data are divided over multiple blocks, the affected blocks being joined to form a sequence, i.e., a linked list. Therefore, a block also contains information as to whether the block is the first in the sequence, and optionally, which block is next in the sequence.
The conventional search for a concrete datum in the block-oriented file system is conducted as follows. All blocks in the storage medium are searched in a given sequence, for example from the first to the last block, until a block is found which meets the following criteria: The block is occupied and is the first block in the sequence, and the identifier for the datum present in the block corresponds to the identifier for the searched datum.
This results in two possibilities: a) If such a block is found, the searched datum may be read. All other blocks relevant to the datum are found via the linkage of blocks, from the predecessor to the successor. b) If no such block is found, the searched datum is not present on the storage medium.
One problem with this conventional method is the potentially long time required for reading multiple data. If each datum is individually requested, the search must be conducted each time over all the blocks in the storage medium. If, for example, the distribution of the data over the storage medium is assumed to be random, it is expected that (b+1)/2 blocks must be searched until the sought datum is found in the search for a datum on a block-oriented file system containing b blocks. For d data to be searched for, this results in a number of d*(b+1)/2 blocks to be searched. On a worst-case basis, however, it is not possible for this number to be higher.
A problem with this number of blocks to be searched, and the associated computing time, is the fact that for control units most of the data in the system must typically be read in the startup phase. However, the computing time available for this startup phase is usually very short.